package leetcode.code078;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution extends Solution078 {

	@Override
	public List<List<Integer>> subsets(int[] nums) {
		List<Integer> list = new ArrayList<>();
		Map<Integer, List<List<Integer>>> cache = new HashMap<>();
		subsets(nums, 0, cache);
		cache.get(0).add(list);
		return cache.get(0);
	}

	public List<List<Integer>> subsets(int[] nums, int index, Map<Integer, List<List<Integer>>> cache) {
		if (cache.containsKey(index)) {
			return cache.get(index);
		}
		List<List<Integer>> result = new ArrayList<>();
		if (index == nums.length) {
			return result;
		}
		Integer cur = nums[index];
		List<Integer> temp = new ArrayList<>();
		temp.add(cur);
		result.add(temp);// 当前
		List<List<Integer>> sublist = subsets(nums, index + 1, cache);
		for (List<Integer> sub : sublist) {// 当前组合之前数据
			temp = new ArrayList<>();// <<<
			temp.add(cur);
			temp.addAll(sub);
			result.add(temp);
//			sub.add(cur);
//			result.add(sub);
		}
		result.addAll(sublist);// 之前数据
		cache.put(index, result);
		return result;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();

	}

}
